package com.tys.algorithm.bak.code1;

// https://leetcode.com/problems/count-of-range-sum/
// 给你一个整数数组 nums 以及两个整数 lower 和 upper 。
// 求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数
// 区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
public class Code24_CountOfRangeSum {


    public static int countRangeSum(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        //生成前缀和
        long[] sum = new long[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        return process(sum, 0, sum.length - 1, lower, upper);
    }

    //arr[L...R] 不传，只传sum， 求arr[L...R]中有多少子数组累加和在[lower,upper]上
    //sum代表
    public static int process(long[] sum, int L, int R, int lower, int upper) {
        //0...L 前缀和在[lower,upper]上
        if (L == R) {
            return sum[L] >= lower && sum[L] <= upper ? 1 : 0;
        }
        int M = L + ((R - L) >> 1);
        return process(sum, L, M, lower, upper)
                + process(sum, M + 1, R, lower, upper)
                + merge(sum, L, M, R, lower, upper);
    }

    public static int merge(long[] arr, int L, int M, int R, int lower, int upper) {
        int ans = 0;
        //左组滑动窗口
        int windowL = L;
        int windowR = L;
        //遍历右组
        for (int i = M + 1; i <= R; i++) {
            //上限和下限
            long min = arr[i] - upper;
            long max = arr[i] - lower;
            //窗口范围：[min, max)
            //滑动窗口不超过上限和下限
            while (windowR <= M && arr[windowR] <= max) {
                windowR++;
            }
            while (windowL <= M && arr[windowL] < min) {
                windowL++;
            }
            //结果
            ans += windowR - windowL;
        }
        //归并排序
        long[] help = new long[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return ans;
    }
}
